
//#include "fft.h"

//void fft::rev(std::vector<double>& x)
//{ //reverse the sequence in bit order.
//    int len=log2(N);
//    int idd,ret,bit;
//    for (int i=0; i<N; i++){
//        idd=i; ret=0;
//        for (int j=0; j<len; j++){
//            ret = ret << 1;
//            bit = idd & 1;
//            idd = idd >> 1;
//            ret = bit | ret;
//        }
//        u[i]=x[ret];
//    }
//    for (int i=0; i<N; i++)
//        x[i]=u[i];
//}

//Complex fft::Wn(double A,double B){
//    Complex u;
//    u.a=cos((2*pi/A)*B); u.b=-sin((2*pi/A)*B);
//    return u;
//}

//void fft::compute(std::vector<double>& x, std::vector<double>& u, int l,int r,int len)
//{
//    Complex tmp;
//    int n=len/2;
//    if (len<2) return; //Level 1

//    fft(x, u, l,l+n-1,n); //even seg process
//    fft(x, u, l+n,r,n);	//odd seg process

//    for (int i=l; i<=r; i++)
//    {
//        if (i < l+n){
//            u[i] = x[i] + W[(i-l)*(N/len)] * x[i+n];
//        }
//        else{
//            x[i] = x[i-n] - x[i] * W[(i-n-l)*(N/len)];
//            x[i-n]=u[i-n];
//        }
//    }
//    return;
//}
//std::vector<Complex> fft::compute(const std::vector<double>& x)
//{
//    std::vector<Complex> xx(x);
//    rev(xx);
//    std::vector<Complex> u(x.size(), Complex(0,0));
//    fft(xx, u, 0, x.size()-1, x.size());
//    return xx;
//}
